﻿using System;

/*
2021-03-02 JackLee
https://leetcode-cn.com/problems/range-sum-query-2d-immutable/

解题思路：
上次求一维数组的区域和检索时，利用了一维数组的前缀和，那么这里
    1.可以利用一维前缀和，再遍历行进行相加求解，【此时时间复杂度为O(mn)，构建复杂度为O(n)，查找的复杂度为O(1)】
    2.为了降低查找的时间复杂度，可以再这里对二维数组进行前缀和处理。
        求前缀和：f(i,j)=f(i-1,j)+f(i,j-1)+array[i,j]-f(i-1,j-1)【f(i-1,j)和f(i,j-1)有重合部分f(i-1,j-1)】
        求解时
            f(i,j,i1,j1)=f(i1,j1)-f(i1,j)-f(i,j1)+f(i,j)
            再存储前缀和时，我们知道要将前n个元素的和存储再位置n，因此实例化一个array[m+1][n+1]的数组


*/
namespace RangeSumQuery2D
{
    public class NumMatrix
    {
        int[][] sums;
        public NumMatrix(int[][] matrix)
        {
            int rows=matrix.Length;
            if(rows>0)
            {
                int clos=matrix[0].Length;
                sums=new int[rows+1][];
                for(int i=0;i<=rows;i++)
                {
                    sums[i]=new int[clos+1];
                }

                for(int i=0;i<rows;i++)
                {
                    for(int j=0;j<clos;j++)
                    {
                        sums[i+1][j+1]=sums[i+1][j]+sums[i][j+1]-sums[i][j]+matrix[i][j];
                    }
                }
            }
        }

        public int SumRegion(int row1, int col1, int row2, int col2)
        {
            return sums[row2+1][col2+1]-sums[row2+1][col1]-sums[row1][col2+1]+sums[row1][col1];
        }
    }
}
